import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class PreFlowPush {
	    private Vertex sink;
	    private SimpleGraph graph;
		private Map<String, Integer> vertexMap;
		private ArrayList<Vertex>[] excessHeightList;
		private List<ArrayList<Edge>> residualEdgeList;
		private List<Integer> edgePointerList;
		private int maxHeight;
				
		// Default PreflowPush constructor.
		 
		@SuppressWarnings("unchecked")
		public PreFlowPush(SimpleGraph G) {
			vertexMap = new HashMap<String, Integer>();
			excessHeightList = new ArrayList[(G.numVertices() + 2)];
			residualEdgeList = new ArrayList<ArrayList<Edge>>(G.numVertices());
			edgePointerList = new ArrayList<Integer>(G.numVertices());
			graph = G;
			maxHeight = 0;
		}
		
		// Calculate the max flow for the graph 
		public int calculateMaxFlow() {
	        Vertex excess_vertex;       
	        
	        while(excessVertices()) {
	        	//Process the first vertex with excess flow at the current maximum height.
	        	excess_vertex = findNextVertex();
	        	boolean pushPossible = push(excess_vertex);
	        	if(!pushPossible) {
	        		relabel(excess_vertex);
	        	}
	        }
			return ((VertexData) sink.getData()).getExcessFlow(); // maximum flow is excess flow at sink
		}
		
		
		//Check for vertices with excess flow 
		
		private boolean excessVertices() {
			boolean VertexWithExcess = false;
			for(int i = 0; i < excessHeightList.length; i++) {
				if(excessHeightList[i] != null) {
					VertexWithExcess= true;
					break;
				}
			}
			
			return VertexWithExcess; 
		}
				
		//Finds the next excess-flow vertex to process.  
				
		private Vertex findNextVertex() {			
			if(excessHeightList[maxHeight] == null) {
				for(int i = maxHeight - 1; i >= 0; i--) {
					if(excessHeightList[i] != null) {
						maxHeight = i;
						break;
					}
				}
			}
			return (Vertex) excessHeightList[maxHeight].get(0); //return top vertex at that height
		}
							
				
	   //Initialization of data structures 
		 
		public void initialize(Vertex s, Vertex t) {
			
			//VertexData data;
	    	EdgeData info;
			Iterator itr;
			Vertex v;
			
			String name;
			int index = 0;
			
			Vertex start = s;
			sink = t;
						
			//initialize all edges with edge data
			EdgeData edgeDataObj; 
			itr = graph.edges();
			for(itr = graph.edges();itr.hasNext();)
			{
				Edge edge = (Edge) itr.next();
				Double capacity = (Double) edge.getData();
				int temp = capacity.intValue();
				try{
			    edgeDataObj = new EdgeData(temp,0);
				edge.setData(edgeDataObj);
				}
				catch (Exception e) {
					e.printStackTrace();
				}
			}
			
			//Initializes all Vertices and data structures
			Iterator<Edge> s_v;
			Edge sIncident_edge;
			
			VertexData vDataObj;
			int n = graph.numVertices();
			for (itr = graph.vertices(); itr.hasNext();){
	             v = (Vertex) itr.next();
	             name = (String) v.getName();
	             residualEdgeList.add(new ArrayList<Edge>()); //residual edge List for every vertex.
		         vertexMap.put(name, index); //update Vertex map with id for each vertex
		         edgePointerList.add(0); //Set the current pointer to vertex's first residual edge.
	             //System.out.println("vertex.name is "+v.getName());
	             vDataObj = new VertexData();
	             if(v== s) {
	            	 vDataObj.setVertexHeight(n);  //set source vertex height
	            	 
	            	 for(s_v = graph.incidentEdges(v); s_v.hasNext();) {
	            		    sIncident_edge = (Edge) s_v.next();
		        			info = new EdgeData();
		        			info = (EdgeData) sIncident_edge.getData();
		        			try {
								info.setFlow(info.getCapacity());
							} catch (Exception e) {
								e.printStackTrace();
							}
		                	
		        		} 
	             }
	             v.setData(vDataObj);
	             index++;
	         }
			
			//String source_name = (String) start.getName();
			excessHeightList[0] = new ArrayList<Vertex>();
			          
	        ArrayList<Edge> residual_edge_list;
	        ArrayList<Vertex> vertex_height_list;
	        
	        //Determine excess flow and residual edges for vertices 
	        for (itr = graph.vertices(); itr.hasNext();) {
	        	int edge_flow;
	        	int inflow = 0;
	        	int outflow = 0;
	        	v = (Vertex) itr.next();
	        	name = (String) v.getName(); //get name of the vertex
	        	residual_edge_list = residualEdgeList.get(vertexMap.get(name));
	        	
	        	for(s_v = graph.incidentEdges(v); s_v.hasNext();) {
	        		sIncident_edge = (Edge) s_v.next();
	        		EdgeData edgeData = new EdgeData();
	        		edge_flow = ((EdgeData) sIncident_edge.getData()).getFlow();
	        	
	        		if(sIncident_edge.getFirstEndpoint()== v){ //outward edge
	        			outflow += edge_flow;
	            		if(edge_flow < ((EdgeData) sIncident_edge.getData()).getCapacity()) {
	            			residual_edge_list.add(sIncident_edge);  // add (v, w) to Residual graph
	        			
	            		}
	            	} else {
	            		inflow += edge_flow; 
	            		if(edge_flow > 0) {
	            			residual_edge_list.add(sIncident_edge);//add backward edge (v, w) to Residual graph.
	            		}
	            	}
	        	}
	        	
	        	residualEdgeList.set(vertexMap.get(name), residual_edge_list);
	        	vDataObj = (VertexData) v.getData();
	        	vDataObj.setExcessFlow(inflow - outflow);
	        	v.setData(vDataObj);
	        	//Add vertices with excess flow into the excess_height list
	        	
	        	if ((inflow - outflow) > 0 && v!=s && v!=t) {	
	        		int height = vDataObj.getVertexHeight();
	        		vertex_height_list = excessHeightList[height];
	        		vertex_height_list.add(v);
	        		excessHeightList[height] = vertex_height_list;
	        	}
	         }
	        
		}
		
		
		//Pushes excess flow on vertex out of vertex through incident residual edges
		
		private boolean push(Vertex v) {
			boolean pushPossible = false;
			int vIndex = vertexMap.get(v.getName().toString());//get index for Vertex
			VertexData vDataObj = (VertexData) v.getData();
			Vertex w = null;
			int wIndex;
			VertexData wDataObj;
			
			List<Edge> vIncidentEdgeList = residualEdgeList.get(vIndex);
			List<Edge> wIncidentEdgeList;
			
			for(int i = edgePointerList.get(vIndex); i < vIncidentEdgeList.size(); i++) {
				boolean forward_edge = false;
				Edge e = vIncidentEdgeList.get(i); //get residual edge incident on v
				EdgeData edgeDataObj = (EdgeData) e.getData();
				if(v == e.getFirstEndpoint()) {
					w = e.getSecondEndpoint(); //Part of forward edge.
					forward_edge = true;
				} else {
					w = e.getFirstEndpoint(); //Part of backward edge.
				}
				wDataObj = (VertexData) w.getData();
				//Check height to Push
				if(vDataObj.getVertexHeight() > wDataObj.getVertexHeight()) {
					pushPossible = true;
					wIndex = vertexMap.get(w.getName().toString());
					wIncidentEdgeList = residualEdgeList.get(wIndex);
					int min;
					if(forward_edge) {
						//The amount of flow that will be pushed forward
						min = Math.min(vDataObj.getExcessFlow(), edgeDataObj.getAvailable());
						if(edgeDataObj.getFlow() == 0) { // if flow on that edge was 0, add to residual edge list of vertex w 
							wIncidentEdgeList.add(e);
						}
					} else {
						//flow that will be pushed backward
						min = ((Math.min(vDataObj.getExcessFlow(), edgeDataObj.getFlow()))) * (-1); //negation helps in calculating edge flow
						if(edgeDataObj.getAvailable() == 0) { // if it is a saturated edge add to w residual list
							wIncidentEdgeList.add(e);
						}
					}
					try {
						edgeDataObj.setFlow(edgeDataObj.getFlow() + min); //set new flow on edge
						// if it is a forward edge and flow =capacity, no flow possible from v on that edge and so remove from V's incident list.
						//if it a backward edge and flow = 0, no flow can be pushed back from v on that edge and so remove from V's incident list
						if((forward_edge && (edgeDataObj.getAvailable() == 0)) ||
						   (!forward_edge && (edgeDataObj.getFlow() == 0))) {
							vIncidentEdgeList.remove(i); 
							residualEdgeList.set(vIndex, (ArrayList<Edge>) vIncidentEdgeList);
						}
					} catch (Exception e1) {
						e1.printStackTrace();
					}
					residualEdgeList.set(wIndex, (ArrayList<Edge>) wIncidentEdgeList);
					
					//update excess flow on vertex v and vertex w. 
					vDataObj.setExcessFlow(vDataObj.getExcessFlow() - Math.abs(min));
					wDataObj.setExcessFlow(wDataObj.getExcessFlow() + Math.abs(min));
					
					//Update Excess heights for V and W if required.
					// If there is no excess flow on V after push, remove from excessHeightList
					if(vDataObj.getExcessFlow() <= 0) {
						ArrayList<Vertex> nodes = excessHeightList[maxHeight];
						nodes.remove(0);
						excessHeightList[maxHeight] =  nodes;
						if(excessHeightList[maxHeight].size() == 0 && maxHeight != 0) {
							maxHeight = maxHeight - 1;
							excessHeightList[maxHeight + 1] = null;
						}
					}
					
					//If vertex W is not source or sink and has excess because of push, then add to excessHeights
					int wExcessFlow = wDataObj.getExcessFlow();
					if(wExcessFlow > 0  && (wExcessFlow - Math.abs(min)) <= 0 && (w != sink) &&
							   (wIndex != 0)) {
						ArrayList<Vertex> height = excessHeightList[wDataObj.getVertexHeight()];
						if(height == null) {
							height = new ArrayList<Vertex>();
							height.add(w);
							excessHeightList[wDataObj.getVertexHeight()] = height;
						} else {
							excessHeightList[wDataObj.getVertexHeight()].add(w);
						}
					}
					
					v.setData(vDataObj);
					w.setData(wDataObj);
					e.setData(edgeDataObj);
					
					break;
				}
				edgePointerList.set(vIndex, edgePointerList.get(vIndex) + 1);
			}
			return pushPossible;
		}
		
		//Relabel Vertex V
		private void relabel(Vertex v) {
			int vIndex = vertexMap.get(v.getName().toString());
			VertexData vDataObj = (VertexData) v.getData();
			int oldHeight = vDataObj.getVertexHeight();
			int minHeight = graph.numVertices();
			int neighborHeight;
			
			String name = v.getName().toString();
			boolean hasHeight = true;
			
			if(vDataObj.getExcessFlow() <= 0)
			{
				hasHeight = false;
			}
			
			//Finds the neighboring vertex with the smallest height among the set of neighbors. 
			for(Edge neighborEdge : residualEdgeList.get(vIndex)) {
				
				neighborHeight = ((VertexData)graph.opposite(v, neighborEdge).getData()).getVertexHeight();
								
				if(neighborHeight < minHeight) {
					minHeight = neighborHeight;
				}
			}
				
			
			vDataObj.setVertexHeight(minHeight + 1); //set V height to be one more than its minimum height neighbor
			maxHeight = minHeight + 1;
			v.setData(vDataObj);
			edgePointerList.set(vIndex, 0);
			ArrayList<Vertex> vertex_height_list = new ArrayList<Vertex>();
			vertex_height_list.add(v);
			if(excessHeightList[maxHeight] == null) {
				excessHeightList[maxHeight] = vertex_height_list;
			}
			
			//Removes v from its old height list.
			ArrayList<Vertex> vertexListOfHeight = excessHeightList[oldHeight];
			for(int i = 0; i < vertexListOfHeight.size(); i++) {
				if(vertexListOfHeight.get(i).getName().toString().equals(v.getName().toString())) {
					vertexListOfHeight.remove(i);
					if(vertexListOfHeight.size() == 0) {
						excessHeightList[oldHeight] = null;
					} else {
						excessHeightList[oldHeight] = vertexListOfHeight;
					}
				}
			}
						
		}
		
		
		public static void main(String[] args) {
			SimpleGraph G = new SimpleGraph();
			int maxflow;
			Vertex s=null, t=null;
			EdgeData edata;
			Edge e;
			Iterator i;
			long startTime,endTime;
			try {
//				Hashtable<String,Vertex> table = new Hashtable<String,Vertex>();
//		        GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t10-min5-max10.txt");
//		        table = GraphInput.LoadSimpleGraph(G,"Bipartite/s10-t10-min5-max10.txt");
//		        Vertex source = table.get("s");
//		        Vertex sink = table.get("t");
		        
//				G = new SimpleGraph();
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t10-min5-max10.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t300-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t1000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10-t10000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t50-min1-max100.txt");
				GraphInput.LoadSimpleGraph(G, "100-70%-1-100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t1000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t10000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t10000-min1-max1000.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t10000-min50-max10000.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t10000-min250-max10000.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s50-t10000-min1000-max10000.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s100-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s100-t300-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s100-t1000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s100-t10000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s300-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s300-t300-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s300-t1000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s300-t10000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s1000-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s1000-t300-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s1000-t1000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s1000-t10000-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s2000-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s2000-t100-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s2000-t300-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s2000-t500-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10000-t50-min1-max100.txt");
//				GraphInput.LoadSimpleGraph(G, "Bipartite/s10000-t100-min1-max100.txt");
		        for (i = G.vertices(); i.hasNext();) {
					Vertex v = (Vertex) i.next();
					if (v.getName().equals("s"))
						s = v;
					else if (v.getName().equals("t"))
						t = v;
				}
		        
		        
				PreFlowPush model = new PreFlowPush(G);
				model.initialize(s,t);
				
				startTime = System.currentTimeMillis();
				maxflow = model.calculateMaxFlow();
			    endTime = System.currentTimeMillis();
				
			} catch (Exception e1) {
				System.out.println(" There is a problem ");
				e1.printStackTrace();
				return;
			}
//			
//			for (i = G.edges(); i.hasNext(); ) {
//				e = (Edge) i.next();
//				edata = (EdgeData) e.getData();
//				System.out.println("Edge: " + e.getName() + " " 
//						+ e.getFirstEndpoint().getName() + "-" 
//						+ e.getSecondEndpoint().getName() + " "
//						+ edata.getFlow() + "/" + edata.getCapacity());
//			}
			System.out.println("max flow: " + maxflow);
			System.out.println("running time: " + (endTime - startTime) + "ms");
		}
	

}
